package com.cwj.lab3;

import com.cwj.lab1.myArrayList;

import java.util.Arrays;

public class Kruskal {
    class Edge implements Comparable<Edge> {
        int u, v, val;
//边表的结点，不仅仅用来存储结果
        public Edge(int u, int v, int val) {
            this.u = u;
            this.v = v;
            this.val = val;
        }

        @Override
        public String toString() {
            return "{" +
                    "u=" + u +
                    ", v=" + v +
                    ", val=" + val +
                    '}';
        }

        @Override
        public int compareTo(Edge o) {
            return val - o.val;
        }
    }

    private Edge[] edgeList;
//    private myArrayList<Edge>resList=new myArrayList<>();
//用图初始化
    private void init(Graph_matrix graph) {
        this.edgeList = new Edge[graph.getE_num()];
        int V_NUM = graph.getV_num();
        int top = 0;
        for (int i = 0; i < V_NUM; i++) {
            for (int j = i + 1; j < V_NUM; j++) {
                if (graph.getVal(i, j) != graph.getINF()) {
                    edgeList[top++] = new Edge(i, j, graph.getVal(i, j));
                }
            }
        }
    }

    public myArrayList<Edge> getSmallestTree(Graph_matrix graph) {
        //初始化edgeList后，排序
        init(graph);
        //这里可以利用lab4写的排序，但这里为方便就用标志库的，而这里是可以换为任意的lab4实现的排序
        Arrays.sort(edgeList);
        Edge ee = null;
        myArrayList<Edge> resList = new myArrayList<>();
        int V_NUM = graph.getV_num();
        //每次选取的边的两个端点不是同一个连通块的
        //且是每次可以选的边的最小权重的边
        UFset ufset = new UFset(V_NUM);
        for (int j = 0; j < edgeList.length; j++) {
            ee = edgeList[j];
            if (!ufset.isSame(ee.u, ee.v)) {
                resList.addLast(ee);
                ufset.union(ee.u, ee.v);
            }
        }
        return resList;
    }
}
